using System;
using System.Drawing;

namespace System
{
    /// <summary>
    /// Represents a fraction
    /// </summary>
    public class Fraction : IComparable, IFormattable
    {
        private const double defaultAccuracy = 1.0e-5;

        private long n, d;

        /// <summary>
        /// Constructs a fraction from a whole number
        /// </summary>
        /// <param name="number">Whole number</param>
        public Fraction(long number)
            : this(number, 1)
        {
        }

        /// <summary>
        /// Constructs a fraction given the numerator and denominator as whole numbers
        /// </summary>
        /// <param name="numerator">Fractional numerator</param>
        /// <param name="denomonator">Fractional denominator</param>
        public Fraction(long numerator, long denomonator)
        {
            n = numerator;
            d = denomonator;
        }

        /// <summary>
        /// Constructs a fraction from a floating point number
        /// </summary>
        /// <param name="value">Decimal number</param>
        public Fraction(double value)
        {
            Fraction f = FromDouble(value);
            this.n = f.n;
            this.d = f.d;
        }

        /// <summary>
        /// Get/set the denominator
        /// </summary>
        /// <exception cref="ArgumentOutOfRangeException">Thrown if value set to 0</exception>
        public long Denominator
        {
            get { return d; }
            set { if (d == 0) throw new ArgumentOutOfRangeException("value", value, "Denominator cannot be zero."); d = value; }
        }

        /// <summary>
        /// Get/set the numerator
        /// </summary>
        public long Numerator
        {
            get { return n; }
            set { n = value; }
        }

        /// <summary>
        /// Implicit cast to double
        /// </summary>
        /// <param name="f">Fraction</param>
        /// <returns>Double</returns>
        public static implicit operator double(Fraction f)
        {
            return (f.d != 0.0) ? (f.n/(double)f.d) : double.NaN;
        }

        /// <summary>
        /// Tests inequality of two fractions
        /// </summary>
        /// <param name="f1"></param>
        /// <param name="f2"></param>
        /// <returns></returns>
        public static bool operator !=(Fraction f1, Fraction f2)
        {
            return f1.CompareTo(f2) != 0;
        }

        /// <summary>
        /// Multiplies two fractions
        /// </summary>
        /// <param name="f1"></param>
        /// <param name="f2"></param>
        /// <returns></returns>
        public static Fraction operator *(Fraction f1, Fraction f2)
        {
            Fraction f = new Fraction(f1.n*f2.n, f1.d*f2.d);
            f.Reduce();
            return f;
        }

        /// <summary>
        /// Adds two fractions
        /// </summary>
        /// <param name="f1"></param>
        /// <param name="f2"></param>
        /// <returns></returns>
        public static Fraction operator +(Fraction f1, Fraction f2)
        {
            Fraction f = new Fraction(f1.n*f2.d + f2.n*f1.d, f1.d*f2.d);
            f.Reduce();
            return f;
        }

        /// <summary>
        /// Substracts a fraction from another
        /// </summary>
        /// <param name="f1"></param>
        /// <param name="f2"></param>
        /// <returns></returns>
        public static Fraction operator -(Fraction f1, Fraction f2)
        {
            Fraction f = new Fraction(f1.n*f2.d - f2.n*f1.d, f1.d*f2.d);
            f.Reduce();
            return f;
        }

        /// <summary>
        /// Divides two fractions
        /// </summary>
        /// <param name="f1"></param>
        /// <param name="f2"></param>
        /// <returns></returns>
        public static Fraction operator /(Fraction f1, Fraction f2)
        {
            Fraction f = new Fraction(f1.n*f2.d, f1.d*f2.n);
            f.Reduce();
            return f;
        }

        /// <summary>
        /// Tests equality of two fractions
        /// </summary>
        /// <param name="f1"></param>
        /// <param name="f2"></param>
        /// <returns></returns>
        public static bool operator ==(Fraction f1, Fraction f2)
        {
            return f1.CompareTo(f2) == 0;
        }

        /// <summary>
        /// Static function to create a fraction from a double
        /// </summary>
        /// <param name="value">Decimal value</param>
        /// <returns>Fractional equivalent</returns>
        public static Fraction FromDouble(double value)
        {
            long num, den;
            DoubleToFraction(value, out num, out den, defaultAccuracy);
            return new Fraction(num, den);
        }

        /// <summary>
        /// Parses a string into fraction
        /// </summary>
        /// <param name="s"></param>
        /// <param name="style"></param>
        /// <param name="provider"></param>
        /// <returns></returns>
        public static Fraction Parse(string s, System.Globalization.NumberStyles style, IFormatProvider provider)
        {
            string[] parts = s.Split('/');
            if (parts.Length == 0 || parts.Length > 2)
                throw new FormatException();

            long n = long.Parse(parts[0], style, provider);
            long d = (parts.Length == 2) ? long.Parse(parts[1], style, provider) : 1;

            return new Fraction(n, d);
        }

        /// <summary>
        /// Parses a string into fraction
        /// </summary>
        /// <param name="s"></param>
        /// <param name="style"></param>
        /// <returns></returns>
        public static Fraction Parse(string s, System.Globalization.NumberStyles style)
        {
            return Parse(s, style, null);
        }

        /// <summary>
        /// Parses a string into fraction
        /// </summary>
        /// <param name="s"></param>
        /// <param name="provider"></param>
        /// <returns></returns>
        public static Fraction Parse(string s, IFormatProvider provider)
        {
            return Parse(s, System.Globalization.NumberStyles.Integer, provider);
        }

        /// <summary>
        /// Parses a string into fraction
        /// </summary>
        /// <param name="s"></param>
        /// <returns></returns>
        public static Fraction Parse(string s)
        {
            return Parse(s, System.Globalization.NumberStyles.Integer, null);
        }

        /// <summary>
        /// Compares fraction to another
        /// </summary>
        /// <param name="obj"></param>
        /// <returns></returns>
        public int CompareTo(object obj)
        {
            if (!(obj is Fraction))
                throw new ArgumentException("CompareTo can only compare Fraction objects", "obj");
            return ((double)this).CompareTo((double)obj);
        }

        /// <summary>
        /// Overridden. Test equality of two Fractions.
        /// </summary>
        /// <param name="obj">Fraction to compare</param>
        /// <returns>True if obj has same value as object</returns>
        public override bool Equals(object obj)
        {
            return CompareTo(obj) == 0;
        }

        /// <summary>
        /// Overridden. Gets hash code for fraction.
        /// </summary>
        /// <returns>Hash code</returns>
        public override int GetHashCode()
        {
            return ((double)this).GetHashCode();
        }

        /// <summary>
        /// Reduces fraction to simplest form
        /// </summary>
        public void Reduce()
        {
            DoubleToFraction((double)this, out n, out d, defaultAccuracy);
        }

        /// <summary>
        /// Overridden to return string value in the form "numerator/denominator"
        /// </summary>
        /// <returns>String representation of fraction</returns>
        public override string ToString()
        {
            return (d != 0.0) ? String.Concat(n, '/', d) : double.NaN.ToString();
        }

        /// <summary>
        /// Gets string representation of fraction.
        /// </summary>
        /// <param name="format"></param>
        /// <param name="formatProvider"></param>
        /// <returns></returns>
        public string ToString(string format, System.IFormatProvider formatProvider)
        {
            return (d != 0.0) ? n.ToString(format, formatProvider) + '/' + d.ToString(format, formatProvider) : double.NaN.ToString(format, formatProvider);
        }

        /// <summary>
        /// Static function that converts a double value its fractional parts within a give accuracy
        /// </summary>
        /// <remarks>
        /// Extracted from work done by John Kennedy at http://homepage.smc.edu/kennedy_john/DEC2FRAC.PDF.
        /// The value of accuracyFactor is used to determine how accurate the conversion needs to be. For example, if
        /// accuracyFactor 0.0005 then the conversion should be accurate to 3 decimal places. To get accuracy to 5
        /// decimal places set the AccuracyFactor 0.000005. The higher the AccuracyFactor the larger but more
        /// accurate is the fraction that is returned.
        /// </remarks>
        /// <param name="value">Decimal value to convert</param>
        /// <param name="numerator">Returned fractional numerator</param>
        /// <param name="denominator">Returned fractional denominator</param>
        /// <param name="accuracyFactor">Conversion accuracy (see Remarks)</param>
        private static void DoubleToFraction(double value, out long numerator, out long denominator, double accuracyFactor)
        {
            // Save off sign and work with positive number
            long sign = (value < 0.0) ? -1 : 1;
            value = Math.Abs(value);

            // Check for whole numbers
            if (value == (long)value)
            {
                numerator = (long)value*sign;
                denominator = 1;
                return;
            }

            // Check for number too small to represent
            if (value < (1/long.MaxValue))
            {
                numerator = sign;
                denominator = long.MaxValue;
                return;
            }

            // Check for number too big to represent
            if (value > long.MaxValue)
            {
                numerator = long.MaxValue*sign;
                denominator = 1;
                return;
            }

            // Look for best denominator until value is within accuracy or whole
            double Z = value;
            long prevDenominator = 0, temp;
            denominator = 1;
            do
            {
                Z = 1.0/(Z - (long)Z);
                temp = denominator;
                denominator = denominator*((long)Z)+prevDenominator;
                prevDenominator = temp;
                numerator = (long)(value*denominator + 0.5);
            } while ((Math.Abs(value - (numerator/(double)denominator)) >= accuracyFactor) && (Z != (long)Z));

            // Replace sign
            numerator = sign*numerator;
        }
    }

    /// <summary>
    /// Represents a point P in a polor coordinate system
    /// </summary>
    public class PolarPoint
    {
        /// <summary>
        /// Represents a new instance of the PolarPoint class with member data left uninitialized.
        /// </summary>
        public static readonly PolarPoint Empty = new PolarPoint(0.0,0.0);

        private double r;
        private double t;

        /// <summary>
        /// Constructs a polar point given the radius and angle
        /// </summary>
        /// <param name="r">Radius value</param>
        /// <param name="t">Angle (rotation) value</param>
        public PolarPoint(double r, double t)
        {
            this.r = r;
            this.t = t;
        }

        /// <summary>
        /// Constructs a polar point from a Cartesian point
        /// </summary>
        /// <param name="pt"></param>
        public PolarPoint(Point pt)
        {
            PolarPoint pp = FromPoint(pt);
            this.r = pp.r;
            this.t = pp.t;
        }

        /// <summary>
        /// Constructs a polar point from a Cartesian point
        /// </summary>
        /// <param name="pt"></param>
        public PolarPoint(PointF pt)
        {
            PolarPoint pp = FromPoint(pt);
            this.r = pp.r;
            this.t = pp.t;
        }

        /// <summary>
        /// Angle (rotation) of polar coordinate in degrees
        /// </summary>
        public double Angle
        {
            get { return RadiansToDegrees(t); }
            set { t = DegreesToRadians(value); }
        }

        /// <summary>
        /// Radius of polar coordinate
        /// </summary>
        public double R
        {
            get { return r; }
            set { r = value; }
        }

        /// <summary>
        /// Angle (rotation) of polar coordinate in radians
        /// </summary>
        public double T
        {
            get { return t; }
            set { t = value; }
        }

        /// <summary>
        /// Converts degrees to radians
        /// </summary>
        /// <param name="degrees"></param>
        /// <returns></returns>
        public static double DegreesToRadians(double degrees)
        {
            return (degrees/360.0)*2*Math.PI;
        }

        /// <summary>
        /// Creates a PolarPoint from a PointF
        /// </summary>
        /// <param name="pt">Cartesian coordinate point</param>
        /// <returns>Polar coordinate point</returns>
        public static PolarPoint FromPoint(PointF pt)
        {
            double a = Math.Atan(pt.Y/pt.X);
            if (pt.X < 0)
                a += Math.PI;
            else if (pt.X >= 0 && pt.Y < 0)
                a = (2*Math.PI)+a;
            System.Diagnostics.Trace.WriteLine(a, "t");
            return new PolarPoint(Math.Sqrt(Math.Pow(pt.X, 2.0) + Math.Pow(pt.Y, 2.0)), a);
        }

        /// <summary>
        /// Converts radians to degrees
        /// </summary>
        /// <param name="radians"></param>
        /// <returns></returns>
        public static double RadiansToDegrees(double radians)
        {
            return (360*radians)/(2*Math.PI);
        }

        /// <summary>
        /// Tests equality
        /// </summary>
        /// <param name="obj">PolarPoint to compare</param>
        /// <returns>True if points are the same</returns>
        public override bool Equals(object obj)
        {
            if (!(obj is PolarPoint))
                throw new ArgumentException("Equality test can only be performed on other PolarPoints", "obj");
            return (r == ((PolarPoint)obj).r && t == ((PolarPoint)obj).t);
        }

        public override int GetHashCode()
        {
            return ToString().GetHashCode();
        }

        /// <summary>
        /// Tests if fraction has not been assigned
        /// </summary>
        /// <returns>True if fraction is empty</returns>
        public bool IsEmpty()
        {
            return (r == 0.0 && t == 0.0);
        }

        /// <summary>
        /// Creates a PolarPoint from a Point
        /// </summary>
        /// <param name="pt">Cartesian coordinate point</param>
        /// <returns>Polar coordinate point</returns>
        public Point ToPoint()
        {
            return new Point((int)Math.Round(r * Math.Cos(t)), (int)Math.Round(r * Math.Sin(t)));
        }

        /// <summary>
        /// Converts polar coordinate to a string
        /// </summary>
        /// <returns>String representation</returns>
        public override string ToString()
        {
            return String.Format("{0},{1}", r, t);
        }
    }
}